МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«Национальный исследовательский ядерный университет «МИФИ»
Обнинский институт атомной энергетики –
филиал федерального государственного автономного образовательного учреждения высшего образования
«Национальный исследовательский ядерный университет «МИФИ»
(ИАТЭ НИЯУ МИФИ)
,

Одобрено УМС ИАТЭ НИЯУ МИФИ,
Протокол №2-8/2021 От 30.08.2021

РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ

ДИСКРЕТНАЯ МАТЕМАТИКА
( Наименование дисциплины)

01.03.02 – Прикладная математика и информатика
(Код (шифр), наименование направления подготовки (специальности) ФГОС)

Прикладная информатика
(Профиль направления)

Название программы бакалавриата

бакалавр
(Квалификация (степень) выпускника)

очная
Форма обучения (очная, очно-заочная (вечерняя), заочная)

г. Обнинск 20 21 г.

Программа составлена в соответствии с требованиями образовательного стандарта высшего образования национального исследовательского ядерного университета «МИФИ» по направлению подготовки 01.03.02 – Прикладная математика и информатика.

Автор(ы)

З.Х. Насыров, доцент каф. ПМ

Рецензент

Заведующий лаб. Математических методов ФИАЦ ФГБУ «НПО «Тайфун», д.т.н Д. А. Камаев.

Программа рассмотрена на заседании отделения интеллектуальных кибернетических систем (О) (протокол № 5/7 от «30» июля  2021 г.)

Руководитель образовательной программы
01.03.02 – «Прикладная математика и информатика» 
_________________ 	С.В. Ермаков

«____»____________2021  г.

1.	Перечень планируемых результатов обучения по дисциплине, соотнесенных с планируемыми результатами освоения образовательной программы

Целью курса является Формирование необходимой математической базы по алгебре логики, теории множеств, комбинаторике и теории графов для изучения последующих общепрофессиональных и специальных дисциплин.

Задачами изучения курса вляются
Обучение студентов методам и мышлению, характерным для указанных выше разделов дискретной математики на основе изучения лекционного материала и его закрепления с помощью решения задач и упражнений.

В	результате	освоения	ООП	бакалавриата	обучающийся	должен	овладеть следующими результатами обучения по дисциплине:
Коды компетенций	Результаты освоения ООП
Содержание компетенций	Перечень планируемых результатов обучения по дисциплине	
ОПК-1	Способен применять фундаментальные знания, полученные в области математических и (или) естественных наук, и использовать их в профессиональной деятельности	З-ОПК-1 знать естественнонаучные методы познания окружающего мира, знать фундаментальный математический аппарат;
У-ОПК-1 уметь применять естественнонаучные и математические методы исследования различных
явлений, процессов и задач
В-ОПК-1 владеть навыками исследования различных явлений и процессов с использованием естественнонаучного и
математического подхода	
ОПК-3	Способен применять и модифицировать математические модели для решения задач в области профессиональной деятельности	З-ОПК-3 знать принципы построения
математических моделей физических явлений и процессов
У-ОПК-3 уметь формулировать математические модели различных явлений и процессов на основе физических принципов и законов
В-ОПК-3 владеть навыками построения математических моделей физических явлений и процессов	

2.	Место дисциплины в структуре ООП бакалавриата 
3.	Дисциплина реализуется в рамках базовой  части.
Для освоения дисциплины необходимы компетенции, сформированные в рамках изучения следующих дисциплин: математический анализ

Дисциплина изучается на 2 курсе во 3 семестре.

4.	Объем дисциплины в зачетных единицах с указанием количества академических часов, выделенных на контактную работу обучающихся с преподавателем (по видам занятий) и на самостоятельную работу обучающихся

Общая трудоемкость (объем) дисциплины составляет 5 зачетные единицы (з.е.), 180 академических часов.
4.1.	Объём дисциплины по видам учебных занятий (в часах)
Объем дисциплины	Всего часов	
	Очная форма обучения	
Общая трудоемкость дисциплины	180	
Контактная*	работа	обучающихся	с преподавателем
(по видам учебных занятий) (всего)	85	
Аудиторная работа (всего**):	85	
лекции	32	
семинары, практические занятия	32	
Внеаудиторная работа (всего**):	0	
групповая, индивидуальная консультация		
Самостоятельная	работа	обучающихся** (всего)	62	
Вид промежуточной аттестации обучающегося экзамен	54	

5.	Содержание дисциплины, структурированное по темам (разделам) с указанием отведенного на них количества академических часов и видов учебных занятий

5.1.	Разделы дисциплины и трудоемкость по видам учебных занятий (в академических часах)
Для очной формы обучения
№ п/п	Наименование раздела /темы дисциплины	Общая трудоём- кость всего
(в часах)	Виды учебных занятий, включая самостоятельную работу обучающихся и трудоемкость
(в часах)	Формы текущего контроля успевае- мости	
			Аудиторные учебные занятия	

СРО		
			Лек	Сем/Пр	Лаб			
1.	Алгебра логики	44	14	22		8		
1.1.	Операции алгебры логики	8	2	4		2	Проверка на семинаре	
1.2.	Булевы функции, их реализация	16	6	8		2	Проверка на семинаре	
1.3	Полнота систем булевых функций	12	4	6		2	Проверка на семинаре	
1.4	Предикаты, кванторы	8	2	4		2	Проверка на семинаре	
2.	Теория множеств	18	6	8		4		
2.1.	Операции над множествами	8	2	4		2	Проверка на семинаре	
2.2	Отношения на множествах	10	4	4		2	Проверка на семинаре	
3.	Комбинаторика	19	6	9		4		
3.1	Перестановки, размещения,
сочетания…	12	4	6		2	Проверка на семинаре	
3.2	Комбинаторные методы	7	2	3		2	Проверка на семинаре	
4	Теория графов	27	8	12		7		
4.1.	Понятие графа, реализация графов	12	4	6		2	Проверка на семинаре	
4.2.	Характеристики графов	8	2	4		2	Проверка на семинаре	
4.3.	Алгоритмы обхода графов	7	2	2		3	Проверка на семинаре	

5.2.	Содержание дисциплины, структурированное по разделам (темам)

Лекционный курс

№	Наименование раздела /темы дисциплины	Содержание	
1.	Алгебра логики	
1.1.	Операции алгебры логики	Понятие высказывания. Операции дизъюнкции, конъюнкции и отрицания, их свойства. Логическое следование, эквиваленция и сумма по модулю 2, их свойства.	
1.2.	Булевы функции, их реализация	Булевы (переключательные) функции, их количество и способы задания, существенные и фиктивные переменные. Теорема о реализации многочленом Жегалкина булевой функции, заданной таблично. Алгоритм нахождения многочлена Жегалкина для булевой функции, заданной формулой. Теорема о реализации булевой функции в совершенной дизъюнктивной нормальной форме. Конъюнкты, простые конъюнкты. Теорема о сокращенной ДНФ, следствие о минимальной ДНФ. Приведение пропозициональных формул к ДНФ, их минимизация с помощью правил поглощения и образования союзов. Релейно
- контактные схемы. Теорема о построении контактной схемы по заданной функции проводимости.	
1.3.	Полнота систем булевых функций	Определение  полной  системы  булевых  функций;	классы Поста, их замкнутость. Теорема Поста о полноте.	
1.4.	Предикаты, кванторы	Предикат,	его	область	истинности,	операции	над предикатами. Свободные и связанные переменные. Кванторы
существования и всеобщности, их свойства. Предваренная и сколемовская форма предиката.	
2.	Теория множеств	
2.1.	Операции над множествами	Операции пересечения, объединения, разности и симметрической разности множеств, их свойства. Декартово произведение множеств	
2.2.	Отношения на множествах	Бинарное отношение, обратное отношение, дополнение бинарного отношения. Композиция бинарных отношений, свойства. Отношения эквивалентности, разбиение множества на классы эквивалентности. Частично и линейно упорядоченные множества. Функциональные отношения, сюръективные, инъективные и биективные функции, их свойства. Теорема об обратной функции	
3.	Комбинаторика	
3.1.	Перестановки, размещения,
сочетания.	Принцип комбинаторного умножения. Перестановки, размещения, их количество. Размещения и перестановки с повторениями, их количество. Задача о количестве разбиений множества на подмножества с заданным числом элементов. Полиномиальная формула. Сочетания и их свойства, треугольник Паскаля, формула бинома Ньютона. Сочетания с повторениями, их применение к диофантовым уравнениям.	
3.2.	Комбинаторные методы	Формула включений и исключений. Задача о беспорядках. Латинские прямоугольники. Производящие функции,
примеры. Линейные однородные рекуррентности, последовательность Фибоначчи.	
4.	Теория графов	
4.1.	Понятие графа, реализация графов	Определение графа и орграфа, простой граф, теорема о "рукопожатиях", матрица смежности и ее свойства, способы представления графов в ЭВМ. Подграф. Частичный, нулевой, полный и дополнительный граф. Соединение графов. Изоморфизм графов, теорема о реализации графов в трехмерном пространстве. Плоские и планарные графы, теорема о непланарности $K_{3,3}$. Формулировка теоремы Куратовского-Понтрягина.	
4.2.	Характеристики графов	Цепи, теорема о выделении элементарной цепи, связность графа и ее изменение при удалении ребра. Теорема Эйлера о плоских графах, следствия. Теорема об эйлеровых графах, задача о кенигсбергских мостах. Деревья и их свойства. Цикломатическое число графа, монотонность и смысл цикломатического числа. Хроматическое число графа, примеры. Теорема о четырех красках. Теорема о хроматическом многочлене графа.	
4.3.	Алгоритмы обхода графов	Алгоритмы обхода графов в глубину и в ширину.	

Практические/семинарские занятия

№	Наименование раздела /темы
дисциплины	Содержание	
1.	Алгебра логики			
1.1.	Операции алгебры логики		Понятие высказывания. Операции дизъюнкции, конъюнкции и	отрицания,	их	свойства.	Логическое	следование,
эквиваленция и сумма по модулю 2, их свойства.	
1.2.	Булевы функции, их реализация	Нахождение  многочлена  Жегалкина.  Нахождение  ДНФ  и минимальной ДНФ. Релейно - контактные схемы.	
1.3.	Полнота систем булевых функций		Определение полноты систем булевых функций; применение теоремы Поста о полноте.	
1.4.	Предикаты, кванторы	Нахождение области истинности предикатов. Кванторы существования и всеобщности, их свойства. Предваренная и сколемовская форма предиката.	
2.	Теория множеств			
2.1.	Операции над множествами		Операции пересечения, объединения, разности и симметрической разности множеств, их свойства. Декартово
произведение множеств	
2.2.	Отношения на множествах		Бинарные отношения. Отношения эквивалентности, разбиение множества на классы эквивалентности. Частично и линейно упорядоченные множества. Функциональные отношения, сюръективные, инъективные и биективные функции, их свойства.	
3.	Комбинаторика			
3.1.	Перестановки, размещения,
сочетания.		Принцип комбинаторного умножения. Перестановки, размещения, их количество. Размещения и перестановки с повторениями, их количество. Полиномиальная формула.
Сочетания и их свойства, формула бинома Ньютона. Сочетания с повторениями, их применение к диофантовым уравнениям.	
3.2.	Комбинаторные методы		Формула включений и исключений.  Производящие функции. Линейные однородные рекуррентности.	
4.	Теория графов			
4.1.	Понятие графа, реализация графов		Определение графа и орграфа, простой граф, матрица смежности Соединение графов. Изоморфизм графов. Плоские и планарные графы.	
4.2.	Характеристики графов		Цикломатическое и хроматическое число графа. Хроматический многочлен графа.	
4.3.	Алгоритмы обхода графов		Реализация алгоритмов обхода графов в глубину и в ширину.	

6.	Перечень учебно-методического обеспечения для самостоятельной работы обучающихся по дисциплине
1.	Насыров А.З., Насыров З.Х. Дискретная математика. --- Обнинск: ИАТЭ, 2005.
2.	Насыров З.Х. Дискретная математика. --- Обнинск: ИАТЭ, 1999.}

7.	Фонд  оценочных  средств  для  проведения  промежуточной  аттестации обучающихся по дисциплине

7.1.	Паспорт фонда оценочных средств по дисциплине

№ п/п	Контролируемые разделы (темы) дисциплины (результаты по разделам)	Код контролируемой компетенции (или её части) / и ее
формулировка	Наименование оценочного средства	
1.	Алгебра логики	ОПК-1, ОПК-3	Контрольная работа №1, экзамен.	
2.	Теория множеств	ОПК-1, ОПК-3	Контрольная работа №2, экзамен.	
3.	Комбинаторика	ОПК-1, ОПК-3	Контрольная работа №3, экзамен.	
4.	Теория графов	ОПК-1, ОПК-3	Контрольная работа №3, экзамен.	

7.2.	Типовые контрольные задания или иные материалы

7.2.1.	Экзамен
а) типовые вопросы (образец)
1. Дать определение дизъюнкции и конъюнкции, сформулировать их свойства и доказать дистрибутивные свойства для этих операций.
2. Дать определение отношения эквивалентности, сформулировать и доказать теорему о разбиении множества на классы эквивалентности.
3. Дать определение сочетаний с повторениями, вывести формулу для числа сочетаний с повторениями.
б) критерии оценивания компетенций (результатов):
В ответе на каждый вопрос элемент знания оценивается в 40%, а элемент умения — в 60%/
в) описание шкалы оценивания:
Ответы на 1, 2 и 3 вопрос составляют 14, 13 и 13 баллов соответственно.

7.2.2.	Контрольная работа №1
а) типовые задания (образец)
Задание 1. Найдите многочлен Жегалкина и выясните принадлежность классам K_0, K_1, S, L, M для булевой функции f(a,b,c,d)=(0-2,4,6-9,14,15).
Задание 2. Найдите минимальную ДНФ и постройте контактную схему по этой ДНФ для булевой функции g(a,b,c)=ab\to(b\sim ac).
б) критерии оценивания компетенций (результатов):
В ответе на каждый вопрос элемент знания оценивается в 30%, элемент умения — в 40%/, а элемент владения (навыка) – в 30%.
в) описание шкалы оценивания:
Ответы на 1 и 2 вопрос составляют по 10 баллов.

7.2.3.	Контрольная работа №2
а) типовые задания (образец):
Задание 1 Найдите множество всех значений $y$, для которых является истинным предикат $(1\lt y\lt 5)\oplus\exist{x}(x>y)$, если
$x\in[0;4],y\in[0;\infty)$.
Задание 2. Докажите, что $(A\triangle B)\setminus(A\cup\ol C)=(B\cap C)\setminus A$.
Задание 3. Даны бинарные отношения $R_1=\{(a,p),(a,r),(b,q),(b,t),(c,r),(c,t)\}$ и
$R_2=\{(x,p),(y,p),(y,q),(z,q),(z,r),(z,t)\}$.
Найдите $\ol{R_1}\circ R_2^{-1}$, если\\ $R_1\subset A\times P$, а
$R_2\subset B\times P$, где $A=\{a,b,c\}$, $B=\{x,y,z\}$, $P=\{p,q,r,t\}$.
б) критерии оценивания компетенций (результатов):
В ответе на каждый вопрос элемент знания оценивается в 30%, элемент умения — в 40%/, а элемент владения (навыка) – в 30%.
в) описание шкалы оценивания:
Ответы на 1, 2 и 3 вопрос составляют 10, 5 и 5 баллов соответственно.

7.2.4.	Контрольная работа №3
а) типовые задания (образец)
Задание 1. Вычислите значение выражения $2P_3+A_4^2-2C_5^3$. Задание 2. Решите рекуррентность $a_{n+1}=3a_n+2b_n$,
$b_{n+1}=a_n+2b_n$, $a_0=1$, $b_0=2$.
Задание 3. Постройте граф $O_2+K_{2,2}$ и найдите цикломатическое и хроматическое число получившегося графа.
б) критерии оценивания компетенций (результатов):
В ответе на каждый вопрос элемент знания оценивается в 30%, элемент умения — в 40%/, а элемент владения (навыка) – в 30%.
в) описание шкалы оценивания:
Ответы на 1, 2 и 3 вопрос составляют 5, 10 и 5 баллов соответственно.

6.3. Методические материалы, определяющие процедуры оценивания знаний, умений, навыков и (или) опыта деятельности, характеризующих этапы формирования компетенций
Итоговый балл по дисциплине получается суммированием количества баллов набранных по каждой из 3 контрольных работ и баллов за экзамен. Оценка «отлично» ставится за 90 — 100 баллов, «хорошо» за 75 – 89 баллов, «удовлетворительно» за 60 – 74 балла,
«неудовлетворительно» за 0 —59 итоговых баллов.

8.	Перечень основной и дополнительной учебной литературы, необходимой для освоения дисциплины

а) основная учебная литература:
1.	Микони Дискретная математика для бакалавров: множества, отношения, функции, графы, Лань, 2012. - адрес: www.e.landbook.ru
2.	Шевелев Ю.П., Писаренко Л.А., Шевелев М.Ю. Сборник задач по дискретной математике (для практических занятий в группах), Лань, 2013. адрес: www.e.landbook.ru

б) дополнительная учебная литература:

3.	Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.
--- М.:~Энергоатомиздат, 1988.}
4.	Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. --- М.:~Наука, 1992.}
5.	Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. --- М.:~Наука, 1975.}
6.	Холл М. Комбинаторика. --- М.:~Мир, 1970.}
7.	Комбинаторный анализ. Задачи и упражнения./Под ред. К.А. Рыбникова. --- М.:~Наука, 1982.}
8.	Липский В. Комбинаторика для программистов. --- М.: Мир, 1988.}
9.	Зыков А.А. Основы теории графов. --- М.: Наука, 1987.}
10.	Оре О. Теория графов. --- М.: Наука, 1980.}
11.	Харари Ф. Теория графов. --- М.: Мир, 1973.}
12.	Насыров З.Х. Дискретная математика. --- Обнинск: ИАТЭ, 1999.}
13.	Насыров А.З., Насыров З.Х. Дискретная математика. --- Обнинск: ИАТЭ, 2005.
14.	Дискретная математика. Журнал Российской академии наук

8.	Перечень	ресурсов*	информационно-телекоммуникационной	сети
«Интернет» (далее - сеть «Интернет»), необходимых для освоения дисциплины
www.library.mephi.ru , www.e.landbook.ru

9.	Методические указания для обучающихся по освоению дисциплины

Вид учебного занятия	Организация деятельности студента	
Лекция	При изучении дискретной математики следует иметь в виду, что этот раздел высшей математики очень бурно развивается и учебный материал в разных учебных пособиях может сильно отличаться и терминологически и по стилю изложения и по содержанию. Поэтому на первой стадии изучения следует придерживаться материала конспектов лекций и основной литературы. При желании более глубокого изучения можно знакомиться с материалом излагаемым в дополнительной литературе.	
Практические занятия	Для уверенности в правильности решения задачи полезно проверить ответ с помощью альтернативного решения или на частном случае.	
Контрольная работа	Изучить	методические	указания	по	решению	контрольных	задач	и потренироваться на решении аналогических задач.	
Подготовка к экзамену	При  подготовке  к  экзамену  необходимо  ориентироваться  на  конспекты лекций и рекомендуемую  литературу	

10.	Перечень информационных технологий, используемых при осуществлении образовательного процесса по дисциплине, включая перечень программного обеспечения и информационных справочных систем (при необходимости)
Электронная библиотека НИЯУ МИФИ

11.	Описание материально-технической базы, необходимой для осуществления образовательного процесса по дисциплине
Учебная аудитория достаточной вместимости для потока (лекция) или группы (семинары), проектор и ноутбук.

12.	Иные сведения и (или) материалы

12.1.	Перечень образовательных технологий, используемых при осуществлении образовательного процесса по дисциплине
Часов в интерактивной форме – 16.
Планомерная организация последовательности лекций и практических занятий в сочетании с внеаудиторной работой студента. При изложении разделов даются указания на связь с учебным материалом других дисциплин учебного плана, а также практическими приложениями. Систематические индивидуальные консультации.
Интерактивный подход заключается в вовлечении присутствующих студентов в обсуждение рассматриваемых методов решения задачи выработку новых приемов в их решении.

12.2.	Формы организации самостоятельной работы обучающихся (темы, выносимые для самостоятельного изучения; вопросы для самоконтроля; типовые задания для самопроверки

Самостоятельная работа студентов состоит в выполнении домашних заданий в соответствии с темами практических занятий. Контроль осуществляется путем проверки на практических занятиях.

№	Тема самостоятельной работы	Литература	Число часов	
1	Операции алгебры логики	[12]	2	
2	Многочлены Жегалкина	[12]	2	
3	Реализация БФ в ДНФ	[12]	2	
4	Полнота систем булевых функций	[12]	2	
5	Предикаты, кванторы	[12]	2	
6	Множества, отношения, функции	[13]	2	
7	Перестановки, размещения, сочетания	[13]	2	
8	Комбинаторные методы	[13]	2	
9	Понятие графа, реализация графов	[13]	2	
10	Характеристики графов	[13]	2	
11	Алгоритм обхода графа в глубину и в ширину	[13]	3	

12.3.	Краткий терминологический словарь
Не требуется.

1